/**
 * 王强决定把年终奖用于购物，他把想买的物品分为两类：主件与附件
 * 如果要买归类为附件的物品，必须先买该附件所属的主件，且每件物品只能购买一次。
 * 每个主件可以有 0 个、 1 个或 2 个附件。附件不再有从属于自己的附件。
 * 王强查到了每件物品的价格（都是 10 元的整数倍），而他只有 N 元的预算。
 * 除此之外，他给每件物品规定了一个重要度，用整数 1 ~ 5 表示。他希望在花费不超过 N 元的前提下，使自己的满意度达到最大。
 * 满意度是指所购买的每件物品的价格与重要度的乘积的总和。
 * 请你帮助王强计算可获得的最大的满意度。
 * 输入描述：
        输入的第 1 行，为两个正整数N，m，用一个空格隔开：
        （其中 N （ N<32000 ）表示总钱数， m （m <60 ）为可购买的物品的个数。）
        从第 2 行到第 m+1 行，第 j 行给出了编号为 j-1 的物品的基本数据，每行有 3 个非负整数 v p q
        （
            其中 v 表示该物品的价格（ v<10000 ），
            p 表示该物品的重要度（ 1 ~ 5 ），
            q 表示该物品是主件还是附件。如果 q=0 ，表示该物品为主件，如果 q>0 ，表示该物品为附件， q 是所属主件的编号
        ）
 */

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

/**
 * todo 未完成所有用例
 */
class Main {

    int maxMyd = 0;
    int valueLint;
    int numLint;
    List<int[]> goods = new ArrayList<>();
    int[] goodsMyd;
    LinkedList<Integer> indexList = new LinkedList<>();

    public static void main(String[] args) throws IOException {
        try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in))) {
            solution(br);
        }
    }

    private static void solution(BufferedReader br) throws IOException {
        Main cache = new Main();
        String line = br.readLine();
        String[] split = line.split(" ");
        cache.valueLint = Integer.parseInt(split[0]);
        cache.numLint = Integer.parseInt(split[1]);
        cache.goods.add(null);
        while ((line = br.readLine()) != null) {
            int[] good = new int[3];
            split = line.split(" ");
            good[0] = Integer.parseInt(split[0]);
            good[1] = Integer.parseInt(split[1]);
            good[2] = Integer.parseInt(split[2]);
            cache.goods.add(good);
        }
        cache.goodsMyd = new int[cache.goods.size()];
        for (int i = 1; i < cache.goods.size(); i++) {
            int[] good = cache.goods.get(i);
            cache.goodsMyd[i] = good[0]*good[1];
            if (cache.goodsMyd[i]>cache.maxMyd) {
                cache.maxMyd = cache.goodsMyd[i];
            }
            if (good[2] == 0) {
                cache.indexList.addFirst(i);
            } else {
                cache.indexList.addLast(i);
            }
        }
        boolean[] key = new boolean[cache.goods.size()];
        key[0] = true;
        addGoods(cache,0,key,0,0, 0);
        System.out.println(cache.maxMyd);
    }

    static void addGoods(Main main,int index,boolean[] key,int value,int num, int myd){
        if (num >= main.numLint) {
            return;
        }
        num++;
        for (int i = index; i < main.indexList.size(); i++) {
            Integer gi = main.indexList.get(i);
            int[] good = main.goods.get(gi);
            if (!key[good[2]]) {
                continue;
            }
            int newValue = good[0]+value;
            if (newValue > main.valueLint) {
                continue;
            }
            boolean[] nKey = Arrays.copyOf(key, key.length);
            nKey[gi] = true;
            int newMyd = myd+main.goodsMyd[gi];
            if (newMyd > main.maxMyd) {
                main.maxMyd = newMyd;
            }
            addGoods(main,i+1,nKey,newValue,num,newMyd);
        }
    }

}
